package leetcode.editor.cn.q1_300.q50;

import java.util.HashMap;
import java.util.Map;

/**
 * @author qidi
 * @date 2021-12-16 11:16:15
 */
class Q0076_MinimumWindowSubstring {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String minWindow(String s, String t) {
            if (s.length() < t.length()) return "";

            Map<Character, Integer> tMap = new HashMap<>();
            for (int i = 0; i < t.length(); i++) {
                char cc = t.charAt(i);
                Integer num = tMap.getOrDefault(cc, 0);
                tMap.put(cc, num + 1);
            }

            String str = null;

            Map<Character, Integer> sMap = new HashMap<>();

            int l = 0;
            int r = 0;
            while (true) {
                if (check(sMap, tMap)) {
                    // 向左压缩
                    while (l <= r - t.length()) {
                        char cc = s.charAt(l);
                        sMap.put(cc, sMap.get(cc) - 1);
                        if (!check(sMap, tMap)) {
                            if (str == null) {
                                str = s.substring(l, r);
                            } else {
                                if (str.length() > r - l) str = s.substring(l, r);
                            }
                            l++;
                            break;
                        }
                        l++;
                    }
                } else {
                    // 向右扩展
                    if (r == s.length()) break;
                    char cc = s.charAt(r);
                    Integer num = sMap.getOrDefault(cc, 0);
                    sMap.put(cc, num + 1);
                    r++;
                }
            }

            return str == null ? "" : str;
        }

        private boolean check(Map<Character, Integer> sMap, Map<Character, Integer> tMap) {
            for (Map.Entry<Character, Integer> entry : tMap.entrySet()) {
                if (sMap.get(entry.getKey()) == null) return false;
                if (entry.getValue() > sMap.get(entry.getKey())) return false;
            }
            return true;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0076_MinimumWindowSubstring().new Solution();
        System.out.println(solution.minWindow("ADOBECODEBANC", "ABC"));
        System.out.println(solution.minWindow("a", "a"));
        System.out.println(solution.minWindow("a", "aa"));
    }
}